/*
 * @作者: 沙昊
 * @邮箱: shahao@zju.edu.cn
 * @功能: 
 * @包含算法: 
 * Copyright (c) 2023 by 沙昊, All Rights Reserved. 
 */
//爬山，输入：n,m，分别表示一共爬了几天，m表示现存的天数
//输入m组数，[i,j]表示现存的第i天到达的高度j
//输出：若现存记录是有效的，则返回可能到达的最高的高度；若记录是无效的，则返回字符串"IMPOSSIBLE"
//用map<int,int> 记录现存第i天的高度j，用vector记录现存的天数
 
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
 
// class Solution {
//     int cnt;
//     int dis[10][10];
//     int dir_x[4]={0, 1, 0, -1};
//     int dir_y[4]={1, 0, -1, 0};
// public:
//     int orangesRotting(vector<vector<int>>& grid) {
//         queue<pair<int,int> >Q;
//         memset(dis, -1, sizeof(dis));
//         cnt = 0;
//         int n=(int)grid.size(), m=(int)grid[0].size(), ans = 0;
//         for (int i = 0; i < n; ++i){
//             for (int j = 0; j < m; ++j){
//                 if (grid[i][j] == 2){
//                     Q.push(make_pair(i, j));
//                     dis[i][j] = 0;
//                 }
//                 else if (grid[i][j] == 1) cnt += 1;
//             }
//         }
//         while (!Q.empty()){
//             pair<int,int> x = Q.front();Q.pop();
//             for (int i = 0; i < 4; ++i){
//                 int tx = x.first + dir_x[i];
//                 int ty = x.second + dir_y[i];
//                 if (tx < 0|| tx >= n || ty < 0|| ty >= m|| ~dis[tx][ty] || !grid[tx][ty]) continue;
//                 dis[tx][ty] = dis[x.first][x.second] + 1;
//                 Q.push(make_pair(tx, ty));
//                 if (grid[tx][ty] == 1){
//                     cnt -= 1;
//                     ans = dis[tx][ty];
//                     if (!cnt) break;
//                 }
//             }
//         }
//         return cnt ? -1 : ans;
//     }
// };



int main(){
	int n,m;
	cin>>n>>m;
	vector<int> prices(n);
	vector<int> liruns(n);
	vector<int> dp(m+1,0);
	for(int i=0; i<n; i++){
		int price,cost;
		cin>>cost>>price;
		prices[i] = price;
		liruns[i] = price-cost;
	}

	for(int i=0; i<n; i++){
		for(int j=m; j>=prices[i]; j--){
			dp[j] = max(dp[j], dp[j - prices[i]] + liruns[i]);
		}
	}

	cout<<dp[m]<<endl;


}







// int main()
// {

    
//   int n,m;
//   backFlag://快速返回的-goto
//   while(cin>>n>>m)
//   {
//     map<int,int> vi;//现存天数-高度
// 	vector<int> v(m);//现存天数
// 	// vi.clear();
// 	// v.clear();
	
// 	int d,h;
// 	for(int i=0;i<m;i++)
// 	{
// 	  cin>>d>>h;
// 	  v[m] = d;//用v记录现存的天数
// 	  vi[d]=h;//用vi记录某天的高度
// 	}
// 	//将输入的天数进行排序
// 	sort(v.begin(),v.end());
// 	//首先处理第一个数据到第一天的最大值？？
// 	int Max=vi[v[0]]+v[0]-1;
// 	for(int i=1;i<v.size();i++)
// 	{
// 	  if(abs(vi[v[i]]-vi[v[i-1]])>v[i]-v[i-1])
// 	  {
// 	    cout<<"IMPOSSIBLE";
// 		goto backFlag;
// 	  }
// 	  else
// 	  {
// 	    int tem=(v[i]-v[i-1])/2+(vi[v[i]]+vi[v[i-1]])/2;
// 		if(tem>Max)  Max=tem;
// 	  }
// 	}
// 	//最后处理以下最后一天的值
// 	int temp=vi[v[m-1]]+n-v[m-1];
	
// 	if(temp>Max)
// 	Max=temp;
	
// 	//输出最大值
// 	cout<<Max<<endl;
//   }
// }


// class Solution {
// public:
//     bool check(TreeNode *p, TreeNode *q) {
//         if (!p && !q) return true;
//         if (!p || !q) return false;
//         return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
//     }

//     bool isSymmetric(TreeNode* root) {
//         return check(root, root);
//     }
// };

